package com.test.daily.leetcode.y2021.m10.day1004;

/**
 * findMedianSortedArrays
 *
 * @author Tom on 2021/10/4
 */
public class Algo100403_FindMedianSortedArrays {
    public static void main(String[] args) {
        int[] nums1 = new int[]{1,2,3,4,6,7,8};
        int[] nums2 = new int[]{4,5,6,7,8,9,10};
        double media = findMedianSortedArrays2(nums1, nums2);
        System.out.println("media:" + media);
    }

    public static double findMedianSortedArrays1(int[] nums1, int[] nums2) {
        int[] help = new int[nums1.length + nums2.length];
        int p1 = 0;
        int p2 = 0;
        int i = 0;
        while (p1 < nums1.length && p2 < nums2.length) {
            help[i++] = nums1[p1] < nums2[p2] ? nums1[p1++] : nums2[p2++];
        }
        while (p1 < nums1.length) {
            help[i++] = nums1[p1++];
        }
        while (p2 < nums2.length) {
            help[i++] = nums2[p2++];
        }
        if ((nums1.length + nums2.length) % 2 != 0) {
            return help[(nums1.length + nums2.length) / 2];
        } else {
            return (double) (help[(nums1.length + nums2.length) / 2 - 1] + help[(nums1.length + nums2.length) / 2]) / 2;
        }
    }

    public static double findMedianSortedArrays2(int[] nums1, int[] nums2) {

        return process(nums1, 0, nums1.length - 1, nums2, 0, nums2.length - 1);
    }

    public static double process(int[] nums1, int nums1L, int nums1R, int[] nums2, int nums2L, int nums2R){
        if(nums1L == nums1R || nums2L == nums2R){
            return nums1[nums1L] < nums2[nums2L] ? nums2[nums2L] : nums1[nums1L];
        }
        int[] smallArr = nums1[(nums1L + nums1R)/2 ] > nums2[(nums2L + nums2R)/2 ] ? nums2: nums1;
        int[] bigArr = smallArr == nums1 ? nums2: nums1;
        int smallLength = smallArr.length;
        int bigLength = bigArr.length;
        return process(smallArr, smallLength/2, smallLength -1, bigArr, 0, bigLength /2 -1);
    }
}
